//You need to find the largest value in each row of a binary tree. 
//
// Example: 
// 
//Input: 
//
//          1
//         / \
//        3   2
//       / \   \  
//      5   3   9 
//
//Output: [1, 3, 9]
// 
// 
// Related Topics 树 深度优先搜索 广度优先搜索


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun largestValues(root: TreeNode?): List<Int> {
        val result = java.util.LinkedList<Int>()
        largestValues(root, 0, result)
        return result
    }

    fun largestValues(root: TreeNode?, level:Int, result:java.util.LinkedList<Int>) {
        if (root == null) {
            return
        }
        if (result.size == level) {
            result.add(Int.MIN_VALUE)
        }
        if(root.`val` > result[level]){
            result[level] = root.`val`
        }
        largestValues(root.left, level + 1,result)
        largestValues(root.right, level + 1,result)

    }
}
//leetcode submit region end(Prohibit modification and deletion)
